package hash.t15;

import java.util.*;

public class One {
    public List<List<Integer>> threeSum(int[] nums) {

        // 首先将数组分为 大于0，小于0，等于0的三个数组

        Map<Integer, Integer> valAndTimesBigZeo = new HashMap();
        int bigNums = 0;
        Map<Integer, Integer> valAndTimesEqZeo = new HashMap();
        Map<Integer, Integer> valAndTimesSmaZeo = new HashMap();
        int smaNums = 0;

        for (int num : nums) {
            if (num < 0) {
                valAndTimesSmaZeo.put(num, valAndTimesSmaZeo.getOrDefault(num, 0) + 1);
                smaNums++;
            } else if (num == 0) {
                valAndTimesEqZeo.put(num, valAndTimesEqZeo.getOrDefault(num, 0) + 1);
            } else {
                valAndTimesBigZeo.put(num, valAndTimesBigZeo.getOrDefault(num, 0) + 1);
                bigNums++;
            }
        }

        // 000 的情况
        List<List<Integer>> result = new ArrayList();

        if (valAndTimesEqZeo.size() == 1 && valAndTimesEqZeo.get(0) >= 3) {
            List<Integer> zeoList = new ArrayList(3);
            for (int i = 0; i < 3; i++) {
                zeoList.add(0);
            }
            result.add(zeoList);
        }

        // 两个负数和一个正数的情况 和 一正一负和一个零的情况,得用数组
        int[] smaIntArr = new int[valAndTimesSmaZeo.size()];
        int i = 0;
        for (Map.Entry<Integer, Integer> integerIntegerEntry : valAndTimesSmaZeo.entrySet()) {
            smaIntArr[i] = integerIntegerEntry.getKey();
            i++;
        }

        Set<Integer> smaZeoSet = new HashSet();

        // 得到数组之后，用双指针进行排查
        for (int j = 0; j < smaIntArr.length; j++) {

            if (valAndTimesEqZeo.size() != 0) {
                // 注意一正一负一零的情况
                if (!smaZeoSet.contains(smaIntArr[j])
                        && valAndTimesBigZeo.containsKey(-smaIntArr[j])) {
                    List<Integer> zeoList = new ArrayList(3);
                    zeoList.add(smaIntArr[j]);
                    zeoList.add(0);
                    zeoList.add(-smaIntArr[j]);
                    result.add(zeoList);
                    smaZeoSet.add(smaIntArr[j]);
                }
            }

            for (int k = j + 1; k < smaIntArr.length; k++) {
                // 两负一正
                if (valAndTimesBigZeo.containsKey(-(smaIntArr[j] + smaIntArr[k]))) {
                    List<Integer> zeoList = new ArrayList(3);
                    zeoList.add(smaIntArr[j]);
                    zeoList.add(smaIntArr[k]);
                    zeoList.add(-(smaIntArr[j] + smaIntArr[k]));
                    result.add(zeoList);
                }
            }

            // 两个负数相同的情况
            if (valAndTimesSmaZeo.get(smaIntArr[j]) >= 2) {
                if (valAndTimesBigZeo.containsKey(-(smaIntArr[j] + smaIntArr[j]))) {
                    List<Integer> zeoList = new ArrayList(3);
                    zeoList.add(smaIntArr[j]);
                    zeoList.add(smaIntArr[j]);
                    zeoList.add(-(smaIntArr[j] + smaIntArr[j]));
                    result.add(zeoList);
                }
            }
        }

        int j = 0;
        // 大于0 的数组
        int[] bigIntArr = new int[valAndTimesBigZeo.size()];
        for (Map.Entry<Integer, Integer> integerIntegerEntry : valAndTimesBigZeo.entrySet()) {
            bigIntArr[j] = integerIntegerEntry.getKey();
            j++;
        }

        // 两正一负的情况
        for (int l = 0; l < bigIntArr.length; l++) {
            for (int k = l + 1; k < bigIntArr.length; k++) {
                if (valAndTimesSmaZeo.containsKey(-(bigIntArr[l] + bigIntArr[k]))) {
                    List<Integer> zeoList = new ArrayList(3);
                    zeoList.add(bigIntArr[l]);
                    zeoList.add(bigIntArr[k]);
                    zeoList.add(-(bigIntArr[l] + bigIntArr[k]));
                    result.add(zeoList);
                }
            }

            // 两个正数相同的情况
            if (valAndTimesBigZeo.get(bigIntArr[l]) >= 2
                    && valAndTimesSmaZeo.containsKey(-(bigIntArr[l] + bigIntArr[l]))) {
                List<Integer> zeoList = new ArrayList(3);
                zeoList.add(bigIntArr[l]);
                zeoList.add(bigIntArr[l]);
                zeoList.add(-(bigIntArr[l] + bigIntArr[l]));
                result.add(zeoList);
            }
        }

        return result;

    }
}
